package com.sx.sx1.lintcode.day717;

import java.util.HashMap;
import java.util.Map;

public class LC1844 {

    static class Solution {
        /**
         * @param nums: a list of integer
         * @param k:    an integer
         * @return: return an integer, denote the minimum length of continuous subarrays whose sum equals to k
         */
        public int subarraySumEqualsKII(int[] nums, int k) {
            //k:前缀和  v:该前缀和由前面多少数组成
            Map<Integer, Integer> map = new HashMap<>();
            map.put(0, 0); //非常重要
            int ans = 2147483647; //int 最大值
            int sum =0;
            for (int i = 0; i <nums.length ; i++) {
                sum+= nums[i];
                int diff = sum-k;
                if(map.containsKey(diff)){
                    ans= Math.min(ans,i-map.get(diff)+1);
                }
                map.put(sum,i+1);
            }
            return ans == 2147483647 ? -1 : ans;
        }
    }


    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 2};
        int k = 3;

        int[] nums1 = {2, 1, -1, 4, 2, -3};
        int k1 = 3;

        Solution obj = new Solution();
        System.out.println(obj.subarraySumEqualsKII(nums, k));
        System.out.println(obj.subarraySumEqualsKII(nums1, k1));
    }
}


/*
LintCode-Logo
学习
刷题
题集
群组
内推
VIP
CAT
其他...
搜索题目、标签、题集
邀请有礼
中文
avatar
1844 · 子数组和为K II
算法
中等
通过率
47%
题目
题解24
笔记51
讨论3
排名
记录
描述
给定一个整数数组和一个整数k，你需要找到和为k的最短非空子数组，并返回它的长度。

如果没有这样的子数组，返回-1.

数组中的元素可能小于0

样例
样例1：

输入:
nums = [1,1,1,2] and k = 3
输出:
2
样例2：

输入:
nums = [2,1,-1,4,2,-3] and k = 3
输出:
2
标签
推荐课程

系统设计 System Design 2022版
数据库、API、GFS、视频流等16大系统设计详解，实战练习拿下面试/晋升“拦路虎”
1343/3007
已开启智能提示
发起考试
30 分 00 秒
12345678910
public class Solution {
    /**
     * @param nums: a list of integer
     * @param k: an integer
     * @return: return an integer, denote the minimum length of continuous subarrays whose sum equals to k
     */
    /*
public int subarraySumEqualsKII(int[] nums, int k) {
    // write your code here
}
}
控制台
        历史提交
        您有309条未读消息，请及时查看

 */
